package string;

/**
 * 给你一个由字符 'N'、'S'、'E' 和 'W' 组成的字符串 s，其中 s[i] 表示在无限网格中的移动操作：
 * 'N'：向北移动 1 个单位。
 * 'S'：向南移动 1 个单位。
 * 'E'：向东移动 1 个单位。
 * 'W'：向西移动 1 个单位。
 * 初始时，你位于原点 (0, 0)。你 最多 可以修改 k 个字符为任意四个方向之一。
 * 请找出在 按顺序 执行所有移动操作过程中的 任意时刻 ，所能达到的离原点的 最大曼哈顿距离 。
 * 曼哈顿距离 定义为两个坐标点 (xi, yi) 和 (xj, yj) 的横向距离绝对值与纵向距离绝对值之和，即 |xi - xj| + |yi - yj|。
 * <p>
 * 示例 1：
 * 输入：s = "NWSE", k = 1
 * 输出：3
 * 解释：
 * 将 s[2] 从 'S' 改为 'N' ，字符串 s 变为 "NWNE" 。
 * 移动操作	位置 (x, y)	曼哈顿距离	最大值
 * s[0] == 'N'	(0, 1)	0 + 1 = 1	1
 * s[1] == 'W'	(-1, 1)	1 + 1 = 2	2
 * s[2] == 'N'	(-1, 2)	1 + 2 = 3	3
 * s[3] == 'E'	(0, 2)	0 + 2 = 2	3
 * 执行移动操作过程中，距离原点的最大曼哈顿距离是 3 。
 * <p>
 * 示例 2：
 * 输入：s = "NSWWEW", k = 3
 * 输出：6
 * 解释：
 * 将 s[1] 从 'S' 改为 'N' ，将 s[4] 从 'E' 改为 'W' 。字符串 s 变为 "NNWWWW" 。
 * 执行移动操作过程中，距离原点的最大曼哈顿距离是 6 。
 *
 * @author Jisheng Huang
 * @version 20250620
 */
public class MaxDifference_3443 {
    static int left;

    /**
     * 对于曼哈顿距离，由于水平方向的移动和垂直方向的移动互不影响，我们可以分别计算横纵坐标。
     * 设当前向西走了 a 步，向东走了 b 步。比如 a=2, b=5。
     * 把其中更小的 a 改成向东走，可以让我们离原点更远。（改 b 反而让我们离原点更近）
     * 如果把 a 减少 d，那么 b 就能增大 d，所以修改后的当前位置的横坐标为
     * (b+d)−(a−d)=b−a+2d
     * 如果 b 更小，那么横坐标的绝对值为
     * a−b+2d
     * 综合两种情况，修改后的当前位置横坐标的绝对值为
     * ∣a−b∣+2d
     * 其中 d 为操作次数 k，但至多为 a（把 a 减小为 0）且至多为 b（把 b 减小为 0），即
     * d=min(a,b,k)
     * 然后把 k 减少 d，按照同样的方法继续计算纵坐标。
     * <p>
     * 用修改后的横纵坐标绝对值之和，更新答案的最大值。
     *
     * @param s
     * @param k
     * @return
     */
    public static int maxDifference(String s, int k) {
        int ans = 0;
        int[] cnt = new int['X'];

        for (char ch : s.toCharArray()) {
            ++cnt[ch];
            left = k;
            ans = Math.max(ans, f(cnt['N'], cnt['S']) + f(cnt['E'], cnt['W']));
        }

        return ans;
    }

    public static int f(int a, int b) {
        int d = Math.min(Math.min(a, b), left);
        left -= d;

        return Math.abs(a - b) + d * 2;
    }

    public static void main(String[] args) {
        System.out.println(maxDifference("NWSE", 1));
        System.out.println(maxDifference("NSWWEW", 3));
    }
}
